import java.util.*;

public class Solution310 {

    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        List<Integer>[] adjTable = new List[n];
        int[] outDegrees = new int[n];
        List<Integer> res = Arrays.asList(0);
        
        for(int i = 0; i < n; i++){
            adjTable[i] = new ArrayList<>();
        }
        for(int[] edge : edges){
            int n1 = edge[0], n2 = edge[1];
            outDegrees[n1]++;
            outDegrees[n2]++;
            adjTable[n1].add(n2);
            adjTable[n2].add(n1);
        }

        Queue<Integer> q = new LinkedList<>();
        for(int i = 0; i < n; i++){
            if(outDegrees[i] == 1){
                q.add(i);
            }
        }

        while(!q.isEmpty()){
            res = new ArrayList<>();
            int size = q.size();
            for(int i = 0; i < size; i++){
                Integer tmpNode = q.poll();
                res.add(tmpNode);
                List<Integer> tmpAdj = adjTable[tmpNode];
                for(Integer nextNode : tmpAdj){
                    outDegrees[nextNode]--;
                    if(outDegrees[nextNode] == 1){
                        q.add(nextNode);
                    }
                }
            }
        }
        return res;
    }

    public static void main(String[] args) {
        Solution310 s = new Solution310();
        s.findMinHeightTrees(4, new int[][]{new int[]{1, 0}, new int[]{1, 2}, new int[]{1, 3}});
    }
}
